
//1559.二维网格图中探测器
class Solution {
public:
    bool containsCycle(vector<vector<char>>& grid) {
        int dx[]={-1,1,0,0};  
        int dy[]={0,0,-1,1};
        int n=grid.size(),m=grid[0].size();

        vector<vector<int>> vist(n,vector<int>(m));
        function<bool(int,int,int,int)> dfs=[&](int x,int y,int prev_x,int prev_y)  //prev用来记录上一个位置
        {
            vist[x][y]=1;
            for(int k=0;k<4;k++)
            {
                int a=x+dx[k],b=y+dy[k];
                if(a==prev_x&&b==prev_y) continue;  //如果是上一个位置继续找

                if(a>=0&&a<n&&b>=0&&b<m&&vist[a][b]&&grid[a][b]==grid[x][y]) return true;  //找到满足条件的节点了
                if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==grid[x][y])  if(dfs(a,b,x,y)) return true;
            }
            return false;
        };

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(vist[i][j]) continue;
                if(dfs(i,j,-1,-1)) return true;
            }
        }
        return false;
    }
};